package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/'>祖父节点值为偶数的节点和(Sum of Nodes with Even-Valued Grandparent)</a>
 * <p>给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
 * 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）</p>
 * <p>如果不存在祖父节点值为偶数的节点，那么返回 0 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例1：
 *      输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
 *                              <a color='blue'>6</a>
 *                           /     \
 *                          7       <a color='blue'>8</a>
 *                        /  \    /  \
 *                       <a color='red'>2</a>    <a color='red'>7</a>  <a color='red'>1</a>    <a color='red'>3</a>
 *                      /    / \       \
 *                     9    1   4       <a color='red'>5</a>
 *      输出：18
 *      解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点的数目在 1 到 10^4 之间。</li>
 *     <li>每个节点的值在 1 到 100 之间。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/23 15:51
 */
public class LC1315SumOfNodesWithEvenValuedGrandparent_M {
    static class Solution {
        public int sumEvenGrandparent(TreeNode root) {
            // 使用奇数标记初始父节点和祖父节点值
            return dfs(root, 1, 1);
        }

        private int dfs(TreeNode node, int parentVal, int grandparentVal) {
            // 终止条件：当前节点为空
            if (node == null) {
                return 0;
            }
            // 若祖父节点存在且值为偶数，则累加当前节点的值
            return ((grandparentVal & 1) == 0 ? node.val : 0)
                    + dfs(node.left, node.val, parentVal)
                    + dfs(node.right, node.val, parentVal);
        }

        /*public int sumEvenGrandparent(TreeNode root) {
            return dfs(root, null, null);
        }

        public int dfs(TreeNode currNode, TreeNode parentNode, TreeNode grandparentNode) {
            // 终止条件：当前节点为空
            if (currNode == null) {
                return 0;
            }
            int res = 0;
            // 若祖父节点存在且值为偶数，则累加当前节点的值
            if (grandparentNode != null && (grandparentNode.val & 1) == 0) {
                res += currNode.val;
            }
            // 递归遍历左子树和右子树
            // 对于左子节点，其父节点是当前节点，祖父节点是原父节点
            // 对于右子节点同理
            res = res + dfs(currNode.left, currNode, parentNode) + dfs(currNode.right, currNode, parentNode);
            return res;
        }*/
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.sumEvenGrandparent(
                Generator.buildTree(6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5)
        ));
    }
}